//算术基本定理
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=1000050;
bool prime[N];
int p[N];
int k;
void get_prime(){
    k=0;
    memset(prime,true,sizeof(prime));
    for(int i=2;i<N;i++){
        if(prime[i]){
            p[k++]=i;
            for(int j=2*i;j<N;j+=i){
                prime[j]=false;
            }
        }
    }
}
long long get_factor(long long n){
    long long i;
    long long ans=1;
    for(i=0;i<k && p[i]*p[i]<=n;i++){
        int cnt=0;
        if(n%p[i]==0){
            while(n%p[i]==0){
                cnt++;
                n/=p[i];
            }
        }
        ans=ans*(1+cnt);
    }
    if(n>1){
        ans*=2;
    }
    return ans;
}
int main(void){
    //printf("%lld\n",get_factor(12));
    get_prime();
    int t;
    long long a,b;
    scanf("%d",&t);
    int c=1;
    while(t--){
        scanf("%lld%lld",&a,&b);
        if(b*b>=a){
            printf("Case %d: %d\n",c++,0);
            continue;
        }
        long long ans=get_factor(a);
        for(int i=1;i<b;i++){
            if(a%i==0){
                ans-=2;
            }
        }
        printf("Case %d: %lld\n",c++,ans/2);
    }
}
